/*
 * @lc app=leetcode.cn id=373 lang=typescript
 *
 * [373] 查找和最小的K对数字
 */

// @lc code=start

type GetCompareKey<T> = (x: T) => number;

class PQ<T> {
  keys: T[];
  mapKeysValue: GetCompareKey<T>;
  constructor(mapKeysValue: GetCompareKey<T>) {
    this.keys = [];
    this.mapKeysValue = mapKeysValue;
  }
  insert(key: T) {
    this.keys.push(key);
    this.swin(this.keys.length - 1);
  }
  peek() {
    if (this.size() === 0) return void 0;
    return this.keys[0];
  }
  poll() {
    if (this.size() === 0) return void 0;
    const key = this.keys[0];
    this.swap(0, this.size() - 1);
    this.keys.pop();
    this.sink(0);
    return key;
  }
  less(i: number, j: number): boolean {
    return this.mapKeysValue(this.keys[i]) < this.mapKeysValue(this.keys[j]);
  }
  swap(i: number, j: number) {
    [this.keys[i], this.keys[j]] = [this.keys[j], this.keys[i]];
  }
  size() {
    return this.keys.length;
  }
  swin(i: number) {
    let parent = (i - 1) >> 1;
    while (parent >= 0 && this.less(parent, i)) {
      this.swap(parent, i);
      i = parent;
      parent = (i - 1) >> 1;
    }
  }
  sink(i: number) {
    let child = i * 2 + 1;
    while (child < this.size()) {
      if (child + 1 < this.size() && this.less(child, child + 1)) {
        child++;
      }
      if (this.less(child, i)) break;
      this.swap(child, i);
      i = child;
      child = i * 2 + 1;
    }
  }
  isEmpty() {
    return this.size() === 0;
  }
}

class MINPQ<T> extends PQ<T> {
  less(i: number, j: number): boolean {
    return this.mapKeysValue(this.keys[i]) > this.mapKeysValue(this.keys[j]);
  }
}

function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
  const mapKeysValue = (x: number[]) => nums1[x[0]] + nums2[x[1]];
  const minpq = new MINPQ<number[]>(mapKeysValue);

  // 初始化，将num1的元素下标和num2的第一个元素下标放入minpq
  for (let i = 0; i < Math.min(k, nums1.length); i++) {
    minpq.insert([i, 0]);
  }

  const ans: number[][] = [];
  // 遍历k次或者minpq为空
  while (k > 0 && !minpq.isEmpty()) {
    const [i, j] = minpq.poll();
    ans.push([nums1[i], nums2[j]]);
    // 继续将nums2的下一个元素下标放入minpq
    if (j + 1 < nums2.length) {
      minpq.insert([i, j + 1]);
    }
    k--;
  }

  return ans;
}
// @lc code=end
